package q878_nthMagicalNumber;

public class Solution_1 {
    static final int MOD = 1000000007;
    /*
    第N个神奇数字
    本质在于构建一个函数f(x)
    对于a和b的第N个神奇数字，那么小于等于 x 中能被 a 整除的数的个数为 x/a （向下取整）
    同理 另一个是 x/b 因此第n个就是 x/a + x/b - x/c c是a和b的最小公倍数
    该函数单调递增
    二分法即可解决
     */
    public int nthMagicalNumber(int n, int a, int b) {
        long l = Math.min(a, b);
        long r = (long) n * Math.min(a, b);
        int c = lcm(a, b);
        while (l <= r) {
            long mid = (l + r) / 2;
            long cnt = mid / a + mid / b - mid / c;
            if (cnt >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (int) ((r + 1) % MOD);
    }
    /*
    最小公倍数
     */
    public int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }
    /*
    最大公约数
     */
    public int gcd(int a, int b) {
        return b != 0 ? gcd(b, a % b) : a;
    }
}
